package leetcode.top100;


import utils.ListNode;
import utils.ListUtil;

import java.util.*;

/**
 * 链表排序
 *
 * @since 2019/12/12 0012 下午 9:41
 */
public class Code148_SortLink {

    public static void main(String[] args) {
        ListNode node = new ListNode(1);
        node.next = new ListNode(-1);
        node.next.next = new ListNode(0);
        ListUtil.printLinkedList(node);
        node = sortList(node);
        ListUtil.printLinkedList(node);
    }

    public static ListNode sortList(ListNode head) {
        if (head == null || head.next == null) return head;
//        return doSort1(head);
        return doSort2(head);
    }

    /**
     * 方式4：不用递归的归并，空间 O(1)。自底向上归并。
     */

    /**
     * 方式3：归并。数组的归并需要O(n)空间来辅助，但是链表可以做到不需要开辟新空间。
     * <p>
     * <p>
     * <p>
     * 因为只要改变链表的指针顺序就可对原来链表进行排序。
     * <p>
     * 如果使用递归，那么由递归栈引起的额外空间是O(logn)。
     * <p>
     * 可以优化成迭代，就不会使用额外空间，优化成O(1)
     */
    private static ListNode doSort2(ListNode head) {
        return process(head);
    }

    /**
     * 利用master公式可以算出是O(nlogn)时间复杂度
     * <p>
     * 使用递归的归并。空间O是由递归栈产生的(nlogn)。测试通过！
     * <p>
     * 先分，再和。合的过程方法很多，就是合并两个有序链表的过程。
     * <p>
     * 见{@link Code21_MergeTwoSortedLink}
     * <p>
     * 见{@link Code23_MergeKSortedList}
     *
     * @param head
     * @return
     */
    private static ListNode process(ListNode head) {
        // step1  分
        if (head == null || head.next == null) return head;
        ListNode slow = head;
        ListNode fast = head;
        //slow最后在中间位置：奇数是中间 ，偶数是前一个
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode temp = slow.next;
        //隔断。前一半是head到slow，后一半是temp到tail
        slow.next = null;
        ListNode left = process(head);
        ListNode right = process(temp);
        //step2 合
        return mergeSortedList(left, right);
    }

    private static ListNode mergeSortedList(ListNode left, ListNode right) {
        ListNode cur;
        ListNode res;
        //合并left和right两个有序链表
        cur = new ListNode(-1);
        res = cur;
        while (left != null && right != null) {
            if (left.val < right.val) {
                cur.next = left;
                left = left.next;
            } else {
                cur.next = right;
                right = right.next;
            }
            cur = cur.next;
        }
        //只有一个非空
        cur.next = left==null? right : left;
        return res.next;
    }


    /**
     * 方式1：构建小根堆。遍历放入小根堆，然后重新构建。
     * <p>
     * 时间O(nlogn),空间O(n)
     */
    private static ListNode doSort(ListNode head) {
        ListNode cur = head;
        Queue<ListNode> queue = new PriorityQueue<>(new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                return o1.val - o2.val;
            }
        });
        while (cur != null) {
            queue.add(cur);
            cur = cur.next;
        }
        cur = new ListNode(-1);
        head = cur;
        while (!queue.isEmpty()) {
            ListNode temp = queue.poll();
            System.out.println(temp.val);
            cur.next = temp;
            cur = cur.next;
        }
        //注意这里一定要让cur.next = null。不然会形成闭环。
        cur.next = null;
        return head.next;
    }

    /**
     * 方式2：开辟数组，把链表放入数组，对数组排序，然后重建。
     */
    private static ListNode doSort1(ListNode head) {
        List<ListNode> list = new LinkedList<>();
        ListNode cur = head;
        while (cur != null) {
            list.add(cur);
            cur = cur.next;
        }
        Collections.sort(list, (l1, l2) -> l1.val - l2.val);
        cur = new ListNode(-1);
        head = cur;
        int index = 0;
        while (index < list.size()) {
            cur.next = list.get(index++);
            cur = cur.next;
        }
        cur.next = null;
        return head.next;
    }

}
